//
// Created by hay boy on 2022/7/11.
//

#ifndef ALGORITHMS_SKIPNODE_H
#define ALGORITHMS_SKIPNODE_H

#include <unordered_map>
#include <cmath>
#include <sstream>
#include "../exception/illegalParameterValue.h"
#include "dictionary.h"
//https://www.jianshu.com/p/9d8296562806
using namespace std;
template<class K,class E>
struct SkipNode{
    typedef pair<const K,E> pairType;
    pairType element;
    SkipNode<K,E> **next;//指针数组
    SkipNode(const pairType& thePair,int size):element(thePair){
        next = new SkipNode<K,E>* [size];//级数已经确定
    }
};
template<class K,class E>
class SkipList:public Dictionary<K,E>{
protected:
    float cutOff;//用来确定层数
    int levels;//当前最大的非空链表
    int dSize;//字典的数对个数
    int maxLevel;//允许的最大链表层数
    K tailKey;//最大关键字
    SkipNode<K,E>* headerNode;//头结点指针
    SkipNode<K,E>* tailNode;//尾结点指针
    SkipNode<K,E>** last;//last[i] 表示i层的最后节点
public:
    explicit SkipList(K largeKey,int maxPairs=1000,float prob=0.5);
    ~SkipList(){
        SkipNode<K,E> *nextNode;
        while(headerNode!=tailNode){
            nextNode = headerNode->next[0];
            delete headerNode;
            headerNode = nextNode;
        }
        delete tailNode;
        delete []last;
    }
    bool empty() const{
        return dSize==0;
    }
    int size() const{
        return dSize;
    }
    void clear(){}
    pair<const K,E>* find(const K& theKey) const;
    int level()const;
    SkipNode<int, int> *search(const K& theKey)const;
    void insert(const pair<const K,E>& thePair);
    void erase(const K& theKey);
    void output(ostream& out) const;
};

template<class K, class E>
SkipList<K, E>::SkipList(K largeKey, int maxPairs, float prob) {
    //242
    //构造函数，关键字小于largeKey且数对个数size最多为maxPairs。0<prob<1
    cutOff = prob*RAND_MAX;
    maxLevel = (int)ceil(logf((float)maxPairs)/logf(1/prob))-1;
    levels = 0;//初始化级数
    dSize = 0;
    tailKey = largeKey;

    //生成头结点，尾结点和数组last
    pair<K,E> tailPair;
    tailPair.first = tailKey;
    headerNode = new SkipNode<K,E>(tailPair,maxLevel+1);
    tailNode = new SkipNode<K,E>(tailPair,0);
    last = new SkipNode<K,E>*[maxLevel+1];//插入，搜索所能索引的最大节点
    //链表为空时，任意级联表中的头结点都指向尾结点
    for(int i = 0;i<=maxLevel;i++){
        headerNode->next[i] = tailNode;
    }
}

template<class K, class E>
pair<const K, E> *SkipList<K, E>::find(const K &theKey) const {
    if(theKey>=tailKey){
        return nullptr;
    }
    //位置beforeNode是关键字为theKey的节点之前最右边的位置
    SkipNode<K,E>* beforeNode = headerNode;
    for(int i = levels;i>=0;i--){
        while(beforeNode->next[i]->element.first<theKey){
            beforeNode = beforeNode->next[i];
        }
    }
    if(beforeNode->next[0]->element.first==theKey){
        return &beforeNode->next[0]->element;
    }

    return nullptr;
}

template<class K, class E>
int SkipList<K, E>::level() const {
    int lev = 0;
    while(rand()<=cutOff){
        lev++;
    }
    return (lev<=maxLevel)?lev:maxLevel;
}

template<class K, class E>
SkipNode<int, int> *SkipList<K, E>::search(const K &theKey) const {
    SkipNode<K,E>* beforeNode = headerNode;
    for(int i = levels;i>=0;i--){
        while(beforeNode->next[i]->element.first<theKey){
            beforeNode = beforeNode->next[i];
        }
        last[i] = beforeNode;
    }
    return beforeNode->next[0];
}

template<class K, class E>
void SkipList<K, E>::insert(const pair<const K, E> &thePair) {
    //把数对thePair插入字典，覆盖其关键字相同的已存在的数对
    if(thePair.first>=tailKey){
        ostringstream s;
        s<<"Key = "<<thePair.first<<" Must be < "<<tailKey;
        throw illegalParameterValue(s.str());
    }
    //查看关键字为theKey的数对是否已经存在
    SkipNode<K,E>* theNode = search(thePair.first);
    if(theNode->element.first==thePair.first){
        theNode->element.second = thePair.second;
        return;
    }
    //若不存在，则确定新节点所在的级联表
    int theLevel = level();
    //使级theLevel为<=levels+1
    if(theLevel>levels){
        theLevel = ++levels;
        last[theLevel] = headerNode;
    }
    //在节点theNode之后插入新节点
    SkipNode<K,E>* newNode = new SkipNode<K,E>(thePair,theLevel+1);
    for(int i = 0;i<=theLevel;i++){
        newNode->next[i] = last[i]->next[i];
        last[i]->next[i] = newNode;
    }
    dSize++;
}

template<class K, class E>
void SkipList<K, E>::erase(const K &theKey) {
    if(theKey>=tailKey){
        return;
    }
    SkipNode<K,E>* theNode = search(theKey);
    if(theNode->element.first!=theKey){
        return;
    }
    for(int i = 0;i<=levels&&last[i]->next[i]==theNode;i++){
        last[i]->next[i] = theNode->next[i];
    }
    //更新链表级
    while(levels>0&&headerNode->next[levels]==tailNode){
        levels--;
    }
    delete theNode;
    dSize--;
}


template<class K, class E>
void SkipList<K,E>::output(ostream& out) const
{// Insert the dictionary pairs into the stream out.
    // follow level 0 chain
    for (SkipNode<K,E>* currentNode = headerNode->next[0];
         currentNode != tailNode;
         currentNode = currentNode->next[0])
        out << currentNode->element.first << " "
            << currentNode->element.second << "  ";
}

// overload <<
template <class K, class E>
ostream& operator<<(ostream& out, const SkipList<K,E>& x)
{
    x.output(out);
    return out;
}
#endif //ALGORITHMS_SKIPNODE_H
